#include "BinaryTree.h"

BinaryTree::BinaryTree()
{
    root = nullptr; // 初始化为空
}

void BinaryTree::Insert(const ElementType& element)
{
    root = InsertNode(root,element);
}

void BinaryTree::show()
{
    std::cout<<"前";
    PrevTraval(root);
    std::cout<<std::endl;
    std::cout<<"中";
    MidTraval(root);
    std::cout<<std::endl;
    std::cout<<"后";
    PostTraval(root);
    std::cout<<std::endl;

    std::cout<<"序";
    HeightTravel();
    std::cout<<std::endl;
}



void BinaryTree::Remove(const ElementType &element)
{
    root = RemoveNode(root,element);
}

BinaryTree::ElementType *BinaryTree::FindByElement(const ElementType &element)
{
    return FindNode(root,element);
}

BinaryTree::Node *BinaryTree::InsertNode(Node *node, const ElementType &element)
{
    //找到要插入的位置
    if(node == nullptr)
    {
        return new Node(element);
    }
    //如果插入的元素已经存在，二叉排序树不放置相同数据
    if(node->data == element)
    {
        return node;
    }
   
    if(node->data > element)
    {
        //递归插入左子树
        node->left = InsertNode(node->left,element);

        //左边重
        if(LRDevition(node) > 1 )
        {
            //左左
            if(node->left->data > element)
            {
                //右旋
                node = RotateRight(node);
            }
            else //左右
            {
                node = RotateLeftRight(node);
            }
        }


    }
    
    if(node->data < element)
    {
        //递归插入右子树
        node->right = InsertNode(node->right,element);

        if(LRDevition(node) < -1)//右边重
        {

            if(node->right->data < element)// 右右
            {
                //左旋
                node = RotateLeft(node);
            }
            else
            {
                //右左
                node = RotateRightLeft(node);

            }
        }

    }
    return node;
}


BinaryTree::Node *BinaryTree::RemoveNode(Node *node, const ElementType &element)
{
    if(node == nullptr)
        return nullptr;
    
    if(node->data < element)
    {
        node->right = RemoveNode(node->right,element);

    }
    
    else if(node->data > element)
    {
  
        
        node->left = RemoveNode(node->left,element);
    }
    
    else
    {
        //叶子节点
        if(node->left == nullptr && node->right == nullptr)
        {
            delete node;
            return nullptr;
        }
        //有两个孩子
        else if(node->left != nullptr && node->right != nullptr)
        {
            //通常做法是找到右子树的最小值
            Node* minnode = GetMinNode(node->right);
            
            //把最小值给到要删除的结点
            node->data = minnode->data;

            // 删除右子树的最小结点
            node->right = RemoveNode(node->right,minnode->data);

        }

        //有一个孩子,把孩子  接给自己的 双亲结点
        else
        {
            Node* child = node->left ? node->left : node->right;
            delete node;
            node = child;
        }
    }
    
    if(LRDevition(node) > 1)
    {
            //左左
        if(LRDevition(node->left) > 0)
        {
            node = RotateRight(node);
        }
        else
        {
            //左右
            node = RotateLeftRight(node);
        }
    }
    
    else if(LRDevition(node) < -1)//右边重
    {
        if(LRDevition(node->right) > 0)//右左
        {
            node = RotateLeftRight(node);
        }
        else//右右
        {
            node = RotateLeft(node);
        }
    }
    return node;

}

BinaryTree::Node *BinaryTree::GetMinNode(Node *node)
{
    BinaryTree::Node* min = node;
    while(min->left)
        min = min->left;
           
    return min;
}

BinaryTree::ElementType *BinaryTree::FindNode(Node *node, const ElementType &element)
{
    if(node == nullptr)
        return nullptr;
    else if(node->data == element)
        return &node->data;
    else if(node->data < element)
        return FindNode(node->right,element);
    else
    {
        return FindNode(node->left,element);
    }
    
}

void BinaryTree::HeightTravel()
{
    LinkQueue q;
    q.Push(root);
    while(!q.IsEmpty())
    {
        Node *node = (Node*)*q.GetFront();
        
        std::cout<<node->data<<" ";
        
        if(node->left)
        {
            q.Push(node->left);
        }
        if(node->right)
        {
            q.Push(node->right);
        }
        q.Pop();
    }
    std::cout<<std::endl;
}

BinaryTree::Node *BinaryTree::RotateRight(Node *node)
{
    Node* p = node->left;
    node->left = p->right;
    p->right = node;
    return p;
}

BinaryTree::Node *BinaryTree::RotateLeft(Node *node)
{
    Node*p = node->right;
    node->right = p->left;
    p->left = node;
    return p;
}

BinaryTree::Node *BinaryTree::RotateLeftRight(Node *node)
{
    //左子树左旋
    node->left = RotateLeft(node->left);

    return RotateRight(node);//整体 右旋
}

BinaryTree::Node *BinaryTree::RotateRightLeft(Node *node)
{
    //右子树右旋
    node->right = RotateRight(node->right);
    return RotateLeft(node);//整体 左旋
}

int BinaryTree::GetNodeHeight(Node *node)
{
    if(node == nullptr)
        return 0;
    // 左子树高度
    int leftHeight = GetNodeHeight(node->left);
    
    
    // 右子树高度
    int rightHeight = GetNodeHeight(node->right);
    return (leftHeight > rightHeight ? leftHeight:rightHeight) + 1; 
}

int BinaryTree::LRDevition(Node *node)
{
    if(node == nullptr)
        return 0;
    
    return GetNodeHeight(node->left) - GetNodeHeight(node->right);
}


